//package mypack;

import java.math.BigInteger;

public class mymath {
    
    //x^2 - num = 0 牛顿迭代法求解大数开方
    public static BigInteger BigSqrt(BigInteger num) {
        BigInteger two = new BigInteger("2");
        String tmp = num.toString();
        BigInteger res = new BigInteger(tmp.substring(0, tmp.length()/2 + 1));
        while(num.compareTo(res.pow(2)) < 0)
            res = res.add(num.divide(res)).divide(two);
        return res;
    }
    
    /*
      **二次筛法中计算勒朗德符号并不需要考虑极大数，因为p 是小素数。
    */
    public static boolean Legendre(BigInteger n, BigInteger p) {
        BigInteger tmp = n.mod(p);
        return legendre(tmp.intValue(), p.intValue()) == 1; //将参数转为int,使用legendre(int, int)处理
    }
    
    //此处n,p 小于100，穷举素因子
    public static int legendre(int n, int p) {
        if(n == 1)
            return 1;
        else if(n == 2){
            if(p % 8 == 1 || p % 8 == 7)
                return 1;
            else
                return -1;
        }else if(n == p - 1)
            return 2 - p%4;
        else{
            int res = 1;
            for(int i = 2; i <= n; i++){
                if(isPrime(i) && n % i == 0){
                    int count = 0;
                    while(n % i == 0){
                        count ++;
                        n /= i;
                    }
                    if(count % 2 != 0){
                        if(i == 2 || i == p-1)
                            res = res*legendre(i, p);
                        else{
                            if(i%4 == 3 && p%4 == 3)
                                res = res*legendre(p%i, i)*(-1);
                            else
                                res = res*legendre(p%i, i);
                        }
                    }
                }
            }
            return res;
        }
    }
    
    //100以下的素数，常规方法判断.
    public static boolean isPrime(int n) {
        for(int i = 2; i < n; i ++)
            if(n % i == 0)
                return false;
        return true;
    }

    public static BigInteger BigGcd(BigInteger a, BigInteger b) {
        if(a.compareTo(b) < 0)
            return biggcd(b, a);
        else
            return biggcd(a, b);
    }

    private static BigInteger biggcd(BigInteger a, BigInteger b){
        if(a.mod(b).equals(BigInteger.ZERO))
            return b;
        else
            return BigGcd(b, a.mod(b));
    }

    public static int[][] Tmatrix(int[][] matrix) {
        int[][] tmp = new int[matrix[0].length][matrix.length];
        for(int i = 0; i < matrix[0].length; i++) {
            for(int j = 0; j < matrix.length; j++) {
                tmp[i][j] = matrix[j][i];
            }
        }
        return tmp;
    }

    public static void main(String[] args) {
        //System.out.println(BigSqrt(new BigInteger(args[0])));
        int n = Integer.parseInt(args[0]);
        int p = Integer.parseInt(args[1]);
        System.out.println(legendre(n , p));
    }
}